

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon%2032x32.ico">
  <link rel="icon" href="/img/favicon%2032x32.ico">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
    <meta http-equiv="Content-Security-Policy" content="upgrade-insecure-requests">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="hypocrite30">
  <meta name="keywords" content="">
  
  <title>ConcurrentHashMap源码分析JDK8 - hypocrite30</title>

  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/github-markdown-css@4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@10.4.0/styles/idea.min.css" />
    
  

  
    <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css" />
  



<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_kmeydafke9r.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    var CONFIG = {"hostname":"hypocrite30.gitee.io","root":"/","version":"1.8.9","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"right","visible":"hover","icon":"§"},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"copy_btn":true,"image_zoom":{"enable":true},"toc":{"enable":true,"headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":2},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"baidu":"b5f391eebc7eaea88e68a49d5924e381","google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null}}};
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.3.0"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>Hypocrite30 BLOG</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/links/">
                <i class="iconfont icon-link-fill"></i>
                友链
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner" id="banner" parallax=true
         style="background: url('/img/postPage.jpg') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="page-header text-center fade-in-up">
            <span class="h2" id="subtitle" title="ConcurrentHashMap源码分析JDK8">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2021-08-29 21:51" pubdate>
        2021年8月29日 晚上
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      5k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      90
       分钟
    </span>
  

  
  
    
      <!-- 不蒜子统计文章PV -->
      <span id="busuanzi_container_page_pv" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="busuanzi_value_page_pv"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">ConcurrentHashMap源码分析JDK8</h1>
            
              <p class="note note-info">
                
                  本文最后更新于：2021年8月29日 晚上
                
              </p>
            
            <div class="markdown-body">
              <h2 id="ConcurrentHashMap源码分析JDK8"><a href="#ConcurrentHashMap源码分析JDK8" class="headerlink" title="ConcurrentHashMap源码分析JDK8"></a>ConcurrentHashMap源码分析JDK8</h2><h3 id="一、jdk1-8容器初始化"><a href="#一、jdk1-8容器初始化" class="headerlink" title="一、jdk1.8容器初始化"></a>一、jdk1.8容器初始化</h3><h4 id="1、源码分析"><a href="#1、源码分析" class="headerlink" title="1、源码分析"></a>1、源码分析</h4><blockquote>
<p>在<code>jdk8</code>的<code>ConcurrentHashMap</code>中一共有5个构造方法，这四个构造方法中都没有对内部的数组做初始化， 只是对一些变量的初始值做了处理</p>
<p>jdk8的ConcurrentHashMap的数组初始化是在第一次添加元素时完成</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">//没有维护任何变量的操作，如果调用该方法，数组长度默认是16</span><br><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ConcurrentHashMap</span><span class="hljs-params">()</span> </span>&#123;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">//传递进来一个初始容量，ConcurrentHashMap会基于这个值计算一个比这个值大的2的幂次方数作为初始容量</span><br><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ConcurrentHashMap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (initialCapacity &lt; <span class="hljs-number">0</span>)<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException();<br>    <span class="hljs-keyword">int</span> cap = ((initialCapacity &gt;= (MAXIMUM_CAPACITY &gt;&gt;&gt; <span class="hljs-number">1</span>)) ?<br>               MAXIMUM_CAPACITY :<br>               tableSizeFor(initialCapacity + (initialCapacity &gt;&gt;&gt; <span class="hljs-number">1</span>) + <span class="hljs-number">1</span>)); <span class="hljs-comment">// 1.5n + 1</span><br>    <span class="hljs-keyword">this</span>.sizeCtl = cap;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<blockquote>
<p>📌注意，调用这个方法，得到的初始容量和 <code>HashMap</code> 以及<code>jdk7</code>的<code>ConcurrentHashMap</code>不同，即使你传递的是一个2的幂次方数，该方法计算出来的初始容量依然是<strong>比这个值大</strong>的2的幂次方数</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">//调用四个参数的构造</span><br><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ConcurrentHashMap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity, <span class="hljs-keyword">float</span> loadFactor)</span> </span>&#123;<br>    <span class="hljs-keyword">this</span>(initialCapacity, loadFactor, <span class="hljs-number">1</span>);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">//计算一个大于或者等于给定的容量值，该值是2的幂次方数作为初始容量</span><br><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ConcurrentHashMap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity,</span></span><br><span class="hljs-function"><span class="hljs-params">                         <span class="hljs-keyword">float</span> loadFactor, <span class="hljs-keyword">int</span> concurrencyLevel)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (!(loadFactor &gt; <span class="hljs-number">0.0f</span>) || initialCapacity &lt; <span class="hljs-number">0</span> || concurrencyLevel &lt;= <span class="hljs-number">0</span>)<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException();<br>    <span class="hljs-keyword">if</span> (initialCapacity &lt; concurrencyLevel)   <span class="hljs-comment">// Use at least as many bins</span><br>        initialCapacity = concurrencyLevel;   <span class="hljs-comment">// as estimated threads</span><br>    <span class="hljs-keyword">long</span> size = (<span class="hljs-keyword">long</span>)(<span class="hljs-number">1.0</span> + (<span class="hljs-keyword">long</span>)initialCapacity / loadFactor);<br>    <span class="hljs-keyword">int</span> cap = (size &gt;= (<span class="hljs-keyword">long</span>)MAXIMUM_CAPACITY) ?<br>        MAXIMUM_CAPACITY : tableSizeFor((<span class="hljs-keyword">int</span>)size);<br>    <span class="hljs-keyword">this</span>.sizeCtl = cap;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">//基于一个Map集合，构建一个ConcurrentHashMap</span><br><span class="hljs-comment">//初始容量为16</span><br><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ConcurrentHashMap</span><span class="hljs-params">(Map&lt;? extends K, ? extends V&gt; m)</span> </span>&#123;<br>    <span class="hljs-keyword">this</span>.sizeCtl = DEFAULT_CAPACITY;<br>    putAll(m);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<h4 id="2、sizeCtl含义解释"><a href="#2、sizeCtl含义解释" class="headerlink" title="2、sizeCtl含义解释"></a>2、<code>sizeCtl</code>含义解释</h4><blockquote>
<p><strong>注意：以上这些构造方法中，都涉及到一个变量<code>sizeCtl</code>，这个变量是一个非常重要的变量，而且具有非常丰富的含义，它的值不同，对应的含义也不一样，这里我们先对这个变量不同的值的含义做一下说明，后续源码分析过程中，进一步解释</strong></p>
<p><code>sizeCtl</code>为0，代表数组未初始化， 且数组的初始容量为16</p>
<p><code>sizeCtl</code>为正数，如果数组未初始化，那么其记录的是数组的初始容量，如果数组已经初始化，那么其记录的是数组的扩容阈值0.75n</p>
<p><code>sizeCtl</code>为-1，表示数组正在进行初始化</p>
<p><code>sizeCtl</code>小于0，并且不是-1，表示数组正在扩容， -(1+n)，表示此时有n个线程正在共同完成数组的扩容操作</p>
</blockquote>
<h3 id="二、jdk1-8添加安全"><a href="#二、jdk1-8添加安全" class="headerlink" title="二、jdk1.8添加安全"></a>二、jdk1.8添加安全</h3><h4 id="1、源码分析-1"><a href="#1、源码分析-1" class="headerlink" title="1、源码分析"></a>1、源码分析</h4><h5 id="1-1、添加元素put-putVal方法"><a href="#1-1、添加元素put-putVal方法" class="headerlink" title="1.1、添加元素put/putVal方法"></a>1.1、添加元素put/putVal方法</h5><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">put</span><span class="hljs-params">(K key, V value)</span> </span>&#123;<br>    <span class="hljs-keyword">return</span> putVal(key, value, <span class="hljs-keyword">false</span>);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li><code>CHM</code> 不允许有 <strong>空值或空键</strong></li>
<li><code>int hash = spread(key.hashCode())</code> 扰动函数生成哈希值，<code>(h ^ (h &gt;&gt;&gt; 16)) &amp; HASH_BITS</code>：高十六位参与哈希值运算，同时 <code>&amp; 0x7fffffff</code> 即 <code>0111 1111 1111 1111 1111 1111 1111 1111</code> 高位为0，得到的哈希值必然为 <strong>正数</strong> </li>
<li>在 <code>else</code> 里只对待插入桶 <code>f</code> 加锁，不影响 <code>table</code> 的其他元素，保证了安全和高效</li>
<li>进入 <code>else</code> 后又进行桶头结点的判断，防止其他线程在插入之前，将桶结构树化，因为 树化 <code>treeifyBin</code> 在 <code>synchronized</code> 之外</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">final</span> V <span class="hljs-title">putVal</span><span class="hljs-params">(K key, V value, <span class="hljs-keyword">boolean</span> onlyIfAbsent)</span> </span>&#123;<br>    <span class="hljs-comment">//如果有空值或者空键，直接抛异常</span><br>    <span class="hljs-keyword">if</span> (key == <span class="hljs-keyword">null</span> || value == <span class="hljs-keyword">null</span>) <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NullPointerException();<br>    <span class="hljs-comment">//基于key计算hash值，并进行一定的扰动</span><br>    <span class="hljs-keyword">int</span> hash = spread(key.hashCode());<br>    <span class="hljs-comment">//记录某个桶上元素的个数，如果超过8个，会转成红黑树</span><br>    <span class="hljs-keyword">int</span> binCount = <span class="hljs-number">0</span>;<br>    <span class="hljs-comment">// 死循环</span><br>    <span class="hljs-keyword">for</span> (Node&lt;K,V&gt;[] tab = table;;) &#123;<br>        Node&lt;K,V&gt; f; <span class="hljs-keyword">int</span> n, i, fh;<br>        <span class="hljs-comment">//如果数组还未初始化，先对数组进行初始化</span><br>        <span class="hljs-keyword">if</span> (tab == <span class="hljs-keyword">null</span> || (n = tab.length) == <span class="hljs-number">0</span>)<br>            tab = initTable();<br>	    <span class="hljs-comment">//如果hash计算得到的桶位置没有元素，利用cas将元素添加</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((f = tabAt(tab, i = (n - <span class="hljs-number">1</span>) &amp; hash)) == <span class="hljs-keyword">null</span>) &#123;<br>            <span class="hljs-comment">//cas+自旋（和外侧的for构成自旋循环），添加前再判空，保证元素添加安全</span><br>            <span class="hljs-keyword">if</span> (casTabAt(tab, i, <span class="hljs-keyword">null</span>,<br>                         <span class="hljs-keyword">new</span> Node&lt;K,V&gt;(hash, key, value, <span class="hljs-keyword">null</span>)))<br>                <span class="hljs-keyword">break</span>;                   <span class="hljs-comment">// no lock when adding to empty bin</span><br>        &#125;<br>        <span class="hljs-comment">//如果hash计算得到的桶位置元素的hash值为MOVED，证明正在扩容，那么协助扩容</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((fh = f.hash) == MOVED)<br>            tab = helpTransfer(tab, f);<br>        <span class="hljs-keyword">else</span> &#123;<br>            <span class="hljs-comment">//hash计算的桶位置元素不为空，且当前没有处于扩容操作，进行元素添加</span><br>            V oldVal = <span class="hljs-keyword">null</span>;<br>            <span class="hljs-comment">//对当前桶头结点进行加锁，保证线程安全，执行元素添加操作</span><br>            <span class="hljs-keyword">synchronized</span> (f) &#123;<br>                <span class="hljs-keyword">if</span> (tabAt(tab, i) == f) &#123;<br>                    <span class="hljs-comment">//普通链表节点</span><br>                    <span class="hljs-keyword">if</span> (fh &gt;= <span class="hljs-number">0</span>) &#123;<br>                        binCount = <span class="hljs-number">1</span>;<br>                        <span class="hljs-keyword">for</span> (Node&lt;K,V&gt; e = f;; ++binCount) &#123;<br>                            K ek;<br>                            <span class="hljs-comment">// key相同，则将值覆盖掉「是否覆盖取决于onlyIfAbsent」</span><br>                            <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp;<br>                                ((ek = e.key) == key ||<br>                                 (ek != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(ek)))) &#123;<br>                                oldVal = e.val;<br>                                <span class="hljs-keyword">if</span> (!onlyIfAbsent)<br>                                    e.val = value;<br>                                <span class="hljs-keyword">break</span>;<br>                            &#125;<br>                            Node&lt;K,V&gt; pred = e;<br>                            <span class="hljs-comment">// 尾插法</span><br>                            <span class="hljs-keyword">if</span> ((e = e.next) == <span class="hljs-keyword">null</span>) &#123;<br>                                pred.next = <span class="hljs-keyword">new</span> Node&lt;K,V&gt;(hash, key,<br>                                                          value, <span class="hljs-keyword">null</span>);<br>                                <span class="hljs-keyword">break</span>;<br>                            &#125;<br>                        &#125;<br>                    &#125;<br>                    <span class="hljs-comment">//树结构，将元素添加到红黑树中</span><br>                    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (f <span class="hljs-keyword">instanceof</span> TreeBin) &#123;<br>                        Node&lt;K,V&gt; p;<br>                        binCount = <span class="hljs-number">2</span>;<br>                        <span class="hljs-keyword">if</span> ((p = ((TreeBin&lt;K,V&gt;)f).putTreeVal(hash, key,<br>                                                       value)) != <span class="hljs-keyword">null</span>) &#123;<br>                            oldVal = p.val;<br>                            <span class="hljs-keyword">if</span> (!onlyIfAbsent)<br>                                p.val = value;<br>                        &#125;<br>                    &#125;<br>                &#125;<br>            &#125;<br>            <span class="hljs-keyword">if</span> (binCount != <span class="hljs-number">0</span>) &#123;<br>                <span class="hljs-comment">//链表长度大于/ 等于8，将链表转成红黑树</span><br>                <span class="hljs-keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD)<br>                    treeifyBin(tab, i); <span class="hljs-comment">// 里面还要判断数组长度大于等于64，才会树化</span><br>                <span class="hljs-comment">//如果是重复键，直接将旧值返回</span><br>                <span class="hljs-keyword">if</span> (oldVal != <span class="hljs-keyword">null</span>)<br>                    <span class="hljs-keyword">return</span> oldVal;<br>                <span class="hljs-keyword">break</span>;<br>            &#125;<br>        &#125;<br>    &#125;<br>    <span class="hljs-comment">//添加的是新元素，维护集合长度，并判断是否要进行扩容操作</span><br>    addCount(<span class="hljs-number">1L</span>, binCount);<br>    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<blockquote>
<p>通过以上源码，我们可以看到，当需要添加元素时，会针对当前元素所对应的桶位进行加锁操作，这样一方面保证元素添加时，多线程的安全，同时对某个桶位加锁不会影响其他桶位的操作，进一步提升多线程的并发效率</p>
</blockquote>
<h5 id="1-2、数组初始化，initTable方法"><a href="#1-2、数组初始化，initTable方法" class="headerlink" title="1.2、数组初始化，initTable方法"></a>1.2、数组初始化，initTable方法</h5><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> Node&lt;K,V&gt;[] initTable() &#123;<br>    Node&lt;K,V&gt;[] tab; <span class="hljs-keyword">int</span> sc;<br>    <span class="hljs-comment">//cas+自旋，保证线程安全，对数组进行初始化操作</span><br>    <span class="hljs-keyword">while</span> ((tab = table) == <span class="hljs-keyword">null</span> || tab.length == <span class="hljs-number">0</span>) &#123;<br>        <span class="hljs-comment">//如果sizeCtl的值（-1）小于0，说明此时正在初始化， 让出cpu</span><br>        <span class="hljs-keyword">if</span> ((sc = sizeCtl) &lt; <span class="hljs-number">0</span>)<br>            Thread.yield(); <span class="hljs-comment">// lost initialization race; just spin</span><br>        <span class="hljs-comment">//cas修改sizeCtl的值为-1，修改成功，进行数组初始化，失败，继续自旋</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (U.compareAndSwapInt(<span class="hljs-keyword">this</span>, SIZECTL, sc, -<span class="hljs-number">1</span>)) &#123;<br>            <span class="hljs-keyword">try</span> &#123;<br>                <span class="hljs-comment">// double-checked</span><br>                <span class="hljs-keyword">if</span> ((tab = table) == <span class="hljs-keyword">null</span> || tab.length == <span class="hljs-number">0</span>) &#123;<br>                    <span class="hljs-comment">//sizeCtl为0，取默认长度16，否则取sizeCtl的值，即自定义值</span><br>                    <span class="hljs-keyword">int</span> n = (sc &gt; <span class="hljs-number">0</span>) ? sc : DEFAULT_CAPACITY;<br>                    <span class="hljs-meta">@SuppressWarnings(&quot;unchecked&quot;)</span><br>                    <span class="hljs-comment">//基于初始长度，构建数组对象</span><br>                    Node&lt;K,V&gt;[] nt = (Node&lt;K,V&gt;[])<span class="hljs-keyword">new</span> Node&lt;?,?&gt;[n];<br>                    table = tab = nt;<br>                    <span class="hljs-comment">//计算扩容阈值，并赋值给sc</span><br>                    sc = n - (n &gt;&gt;&gt; <span class="hljs-number">2</span>); <span class="hljs-comment">// 0.75n</span><br>                &#125;<br>            &#125; <span class="hljs-keyword">finally</span> &#123;<br>                <span class="hljs-comment">//将扩容阈值，赋值给sizeCtl</span><br>                sizeCtl = sc;<br>            &#125;<br>            <span class="hljs-keyword">break</span>;<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">return</span> tab;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<h4 id="2、图解"><a href="#2、图解" class="headerlink" title="2、图解"></a>2、图解</h4><h5 id="2-1、put加锁图解"><a href="#2-1、put加锁图解" class="headerlink" title="2.1、put加锁图解"></a>2.1、put加锁图解</h5><p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/CHM1.8%E6%B7%BB%E5%8A%A0%E5%AE%89%E5%85%A8.jpg" srcset="/img/loading.gif" lazyload alt="CHM1.8添加安全"></p>
<h3 id="三、jdk1-8扩容安全"><a href="#三、jdk1-8扩容安全" class="headerlink" title="三、jdk1.8扩容安全"></a>三、jdk1.8扩容安全</h3><ul>
<li>线程</li>
</ul>
<h4 id="1、源码分析-2"><a href="#1、源码分析-2" class="headerlink" title="1、源码分析"></a>1、源码分析</h4><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">void</span> <span class="hljs-title">transfer</span><span class="hljs-params">(Node&lt;K,V&gt;[] tab, Node&lt;K,V&gt;[] nextTab)</span> </span>&#123;<br>    <span class="hljs-keyword">int</span> n = tab.length, stride;<br>    <span class="hljs-comment">//如果是多cpu，那么每个线程划分任务，最小任务量是16个桶位的迁移</span><br>    <span class="hljs-keyword">if</span> ((stride = (NCPU &gt; <span class="hljs-number">1</span>) ? (n &gt;&gt;&gt; <span class="hljs-number">3</span>) / NCPU : n) &lt; MIN_TRANSFER_STRIDE)<br>        stride = MIN_TRANSFER_STRIDE; <span class="hljs-comment">// subdivide range</span><br>    <span class="hljs-comment">//如果是扩容线程，此时新数组为null</span><br>    <span class="hljs-keyword">if</span> (nextTab == <span class="hljs-keyword">null</span>) &#123;            <span class="hljs-comment">// initiating</span><br>        <span class="hljs-keyword">try</span> &#123;<br>            <span class="hljs-meta">@SuppressWarnings(&quot;unchecked&quot;)</span><br>            <span class="hljs-comment">//两倍扩容创建新数组</span><br>            Node&lt;K,V&gt;[] nt = (Node&lt;K,V&gt;[])<span class="hljs-keyword">new</span> Node&lt;?,?&gt;[n &lt;&lt; <span class="hljs-number">1</span>];<br>            nextTab = nt;<br>        &#125; <span class="hljs-keyword">catch</span> (Throwable ex) &#123;      <span class="hljs-comment">// try to cope with OOME</span><br>            sizeCtl = Integer.MAX_VALUE;<br>            <span class="hljs-keyword">return</span>;<br>        &#125;<br>        nextTable = nextTab;<br>        <span class="hljs-comment">//记录线程开始迁移的桶位，从后往前迁移</span><br>        transferIndex = n;<br>    &#125;<br>    <span class="hljs-comment">//记录新数组的末尾</span><br>    <span class="hljs-keyword">int</span> nextn = nextTab.length;<br>    <span class="hljs-comment">//已经迁移的桶位，会用这个节点占位（这个节点的hash值为-1--MOVED）</span><br>    ForwardingNode&lt;K,V&gt; fwd = <span class="hljs-keyword">new</span> ForwardingNode&lt;K,V&gt;(nextTab);<br>    <span class="hljs-keyword">boolean</span> advance = <span class="hljs-keyword">true</span>;<br>    <span class="hljs-keyword">boolean</span> finishing = <span class="hljs-keyword">false</span>; <span class="hljs-comment">// to ensure sweep before committing nextTab</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>, bound = <span class="hljs-number">0</span>;;) &#123;<br>        Node&lt;K,V&gt; f; <span class="hljs-keyword">int</span> fh;<br>        <span class="hljs-comment">// 每个线程只迁移一段桶，先计算该线程迁移哪段</span><br>        <span class="hljs-keyword">while</span> (advance) &#123;<br>            <span class="hljs-keyword">int</span> nextIndex, nextBound;<br>            <span class="hljs-comment">//i记录当前正在迁移桶位的索引值</span><br>            <span class="hljs-comment">//bound记录下一次任务迁移的开始桶位</span><br>            <br>            <span class="hljs-comment">//--i &gt;= bound 成立表示当前线程分配的迁移任务还没有完成</span><br>            <span class="hljs-keyword">if</span> (--i &gt;= bound || finishing)<br>                advance = <span class="hljs-keyword">false</span>;<br>            <span class="hljs-comment">//没有元素需要迁移 -- 后续会去将扩容线程数减1，并判断扩容是否完成</span><br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((nextIndex = transferIndex) &lt;= <span class="hljs-number">0</span>) &#123;<br>                i = -<span class="hljs-number">1</span>;<br>                advance = <span class="hljs-keyword">false</span>;<br>            &#125;<br>            <span class="hljs-comment">//计算下一次任务迁移的开始桶位，并将这个值赋值给transferIndex</span><br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (U.compareAndSwapInt<br>                     (<span class="hljs-keyword">this</span>, TRANSFERINDEX, nextIndex,<br>                      nextBound = (nextIndex &gt; stride ?<br>                                   nextIndex - stride : <span class="hljs-number">0</span>))) &#123;<br>                bound = nextBound;<br>                i = nextIndex - <span class="hljs-number">1</span>;<br>                advance = <span class="hljs-keyword">false</span>;<br>            &#125;<br>        &#125;<br>        <span class="hljs-comment">//如果没有更多的需要迁移的桶位，就进入该if</span><br>        <span class="hljs-keyword">if</span> (i &lt; <span class="hljs-number">0</span> || i &gt;= n || i + n &gt;= nextn) &#123;<br>            <span class="hljs-keyword">int</span> sc;<br>            <span class="hljs-comment">//扩容结束后，保存新数组，并重新计算扩容阈值，赋值给sizeCtl</span><br>            <span class="hljs-comment">//这里才是真正的结束扩容，新表替换旧表，重新计算sizeCtl</span><br>            <span class="hljs-keyword">if</span> (finishing) &#123;<br>                nextTable = <span class="hljs-keyword">null</span>;<br>                table = nextTab;<br>                <span class="hljs-comment">//2n-0.5n = 1.5n = 0.75 * 2n，扩容2倍后的下一次扩容阈值</span><br>                sizeCtl = (n &lt;&lt; <span class="hljs-number">1</span>) - (n &gt;&gt;&gt; <span class="hljs-number">1</span>);<br>                <span class="hljs-keyword">return</span>;<br>            &#125;<br>		   <span class="hljs-comment">//扩容任务线程数减1</span><br>            <span class="hljs-keyword">if</span> (U.compareAndSwapInt(<span class="hljs-keyword">this</span>, SIZECTL, sc = sizeCtl, sc - <span class="hljs-number">1</span>)) &#123;<br>                <span class="hljs-comment">//判断当前所有扩容任务线程是否都执行完成</span><br>                <span class="hljs-comment">//在addCount()里最下面的transfer之前，cas将sc赋值为</span><br>                <span class="hljs-comment">//(rs &lt;&lt; RESIZE_STAMP_SHIFT) + 2，与下面判断相同，则证明扩容完毕</span><br>                <span class="hljs-keyword">if</span> ((sc - <span class="hljs-number">2</span>) != resizeStamp(n) &lt;&lt; RESIZE_STAMP_SHIFT)<br>                    <span class="hljs-keyword">return</span>;<br>                <span class="hljs-comment">//所有扩容线程都执行完，标识结束</span><br>                finishing = advance = <span class="hljs-keyword">true</span>;<br>                i = n; <span class="hljs-comment">// recheck before commit</span><br>            &#125;<br>        &#125;<br>        <span class="hljs-comment">//当前迁移的桶位没有元素，直接在该位置添加一个fwd节点</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((f = tabAt(tab, i)) == <span class="hljs-keyword">null</span>)<br>            advance = casTabAt(tab, i, <span class="hljs-keyword">null</span>, fwd);<br>        <span class="hljs-comment">//当前节点已经被迁移</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((fh = f.hash) == MOVED)<br>            advance = <span class="hljs-keyword">true</span>; <span class="hljs-comment">// already processed</span><br>        <span class="hljs-keyword">else</span> &#123;<br>            <span class="hljs-comment">//当前节点需要迁移，加锁迁移，保证多线程安全</span><br>            <span class="hljs-comment">//此处迁移逻辑和jdk7的ConcurrentHashMap相同，不再赘述</span><br>            <span class="hljs-keyword">synchronized</span> (f) &#123;<br>                <span class="hljs-comment">//double-checked，防止桶升级为树结构而出错</span><br>                <span class="hljs-keyword">if</span> (tabAt(tab, i) == f) &#123;<br>                    Node&lt;K,V&gt; ln, hn;<br>                    <span class="hljs-keyword">if</span> (fh &gt;= <span class="hljs-number">0</span>) &#123;<br>                        <span class="hljs-keyword">int</span> runBit = fh &amp; n;<br>                        Node&lt;K,V&gt; lastRun = f;<br>                        <span class="hljs-keyword">for</span> (Node&lt;K,V&gt; p = f.next; p != <span class="hljs-keyword">null</span>; p = p.next) &#123;<br>                            <span class="hljs-keyword">int</span> b = p.hash &amp; n;<br>                            <span class="hljs-keyword">if</span> (b != runBit) &#123;<br>                                runBit = b;<br>                                lastRun = p;<br>                            &#125;<br>                        &#125;<br>                        <span class="hljs-keyword">if</span> (runBit == <span class="hljs-number">0</span>) &#123;<br>                            ln = lastRun;<br>                            hn = <span class="hljs-keyword">null</span>;<br>                        &#125;<br>                        <span class="hljs-keyword">else</span> &#123;<br>                            hn = lastRun;<br>                            ln = <span class="hljs-keyword">null</span>;<br>                        &#125;<br>                        <span class="hljs-keyword">for</span> (Node&lt;K,V&gt; p = f; p != lastRun; p = p.next) &#123;<br>                            <span class="hljs-keyword">int</span> ph = p.hash; K pk = p.key; V pv = p.val;<br>                            <span class="hljs-keyword">if</span> ((ph &amp; n) == <span class="hljs-number">0</span>)<br>                                ln = <span class="hljs-keyword">new</span> Node&lt;K,V&gt;(ph, pk, pv, ln);<br>                            <span class="hljs-keyword">else</span><br>                                hn = <span class="hljs-keyword">new</span> Node&lt;K,V&gt;(ph, pk, pv, hn);<br>                        &#125;<br>                        setTabAt(nextTab, i, ln);<br>                        setTabAt(nextTab, i + n, hn);<br>                        <span class="hljs-comment">//迁移过后，原桶加入fwd</span><br>                        setTabAt(tab, i, fwd);<br>                        advance = <span class="hljs-keyword">true</span>;<br>                    &#125;<br>                    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (f <span class="hljs-keyword">instanceof</span> TreeBin) &#123;<br>                        TreeBin&lt;K,V&gt; t = (TreeBin&lt;K,V&gt;)f;<br>                        TreeNode&lt;K,V&gt; lo = <span class="hljs-keyword">null</span>, loTail = <span class="hljs-keyword">null</span>;<br>                        TreeNode&lt;K,V&gt; hi = <span class="hljs-keyword">null</span>, hiTail = <span class="hljs-keyword">null</span>;<br>                        <span class="hljs-keyword">int</span> lc = <span class="hljs-number">0</span>, hc = <span class="hljs-number">0</span>;<br>                        <span class="hljs-keyword">for</span> (Node&lt;K,V&gt; e = t.first; e != <span class="hljs-keyword">null</span>; e = e.next) &#123;<br>                            <span class="hljs-keyword">int</span> h = e.hash;<br>                            TreeNode&lt;K,V&gt; p = <span class="hljs-keyword">new</span> TreeNode&lt;K,V&gt;<br>                                (h, e.key, e.val, <span class="hljs-keyword">null</span>, <span class="hljs-keyword">null</span>);<br>                            <span class="hljs-keyword">if</span> ((h &amp; n) == <span class="hljs-number">0</span>) &#123;<br>                                <span class="hljs-keyword">if</span> ((p.prev = loTail) == <span class="hljs-keyword">null</span>)<br>                                    lo = p;<br>                                <span class="hljs-keyword">else</span><br>                                    loTail.next = p;<br>                                loTail = p;<br>                                ++lc;<br>                            &#125;<br>                            <span class="hljs-keyword">else</span> &#123;<br>                                <span class="hljs-keyword">if</span> ((p.prev = hiTail) == <span class="hljs-keyword">null</span>)<br>                                    hi = p;<br>                                <span class="hljs-keyword">else</span><br>                                    hiTail.next = p;<br>                                hiTail = p;<br>                                ++hc;<br>                            &#125;<br>                        &#125;<br>                        ln = (lc &lt;= UNTREEIFY_THRESHOLD) ? untreeify(lo) :<br>                            (hc != <span class="hljs-number">0</span>) ? <span class="hljs-keyword">new</span> TreeBin&lt;K,V&gt;(lo) : t;<br>                        hn = (hc &lt;= UNTREEIFY_THRESHOLD) ? untreeify(hi) :<br>                            (lc != <span class="hljs-number">0</span>) ? <span class="hljs-keyword">new</span> TreeBin&lt;K,V&gt;(hi) : t;<br>                        setTabAt(nextTab, i, ln);<br>                        setTabAt(nextTab, i + n, hn);<br>                        setTabAt(tab, i, fwd);<br>                        advance = <span class="hljs-keyword">true</span>;<br>                    &#125;<br>                &#125;<br>            &#125;<br>        &#125;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<h4 id="2、图解-1"><a href="#2、图解-1" class="headerlink" title="2、图解"></a>2、图解</h4><p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/CHM1.8%E6%89%A9%E5%AE%B9%E5%AE%89%E5%85%A8.png" srcset="/img/loading.gif" lazyload alt="CHM1.8扩容安全"></p>
<h3 id="四、jdk1-8多线程扩容效率改进"><a href="#四、jdk1-8多线程扩容效率改进" class="headerlink" title="四、jdk1.8多线程扩容效率改进"></a>四、jdk1.8多线程扩容效率改进</h3><blockquote>
<p>多线程协助扩容的操作会在两个地方被触发：</p>
<p>① 当添加元素时，发现添加的元素对用的桶位为fwd节点，就会先去协助扩容，然后再添加元素</p>
<p>② 当添加完元素后，判断当前元素个数达到了扩容阈值，此时发现sizeCtl的值小于0，并且新数组不为空，这个时候，会去协助扩容</p>
</blockquote>
<h4 id="1、源码分析-3"><a href="#1、源码分析-3" class="headerlink" title="1、源码分析"></a>1、源码分析</h4><h5 id="1-1、元素未添加，先协助扩容，扩容完后再添加元素"><a href="#1-1、元素未添加，先协助扩容，扩容完后再添加元素" class="headerlink" title="1.1、元素未添加，先协助扩容，扩容完后再添加元素"></a>1.1、元素未添加，先协助扩容，扩容完后再添加元素</h5><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">final</span> V <span class="hljs-title">putVal</span><span class="hljs-params">(K key, V value, <span class="hljs-keyword">boolean</span> onlyIfAbsent)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (key == <span class="hljs-keyword">null</span> || value == <span class="hljs-keyword">null</span>) <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NullPointerException();<br>    <span class="hljs-keyword">int</span> hash = spread(key.hashCode());<br>    <span class="hljs-keyword">int</span> binCount = <span class="hljs-number">0</span>;<br>    <span class="hljs-keyword">for</span> (Node&lt;K,V&gt;[] tab = table;;) &#123;<br>        Node&lt;K,V&gt; f; <span class="hljs-keyword">int</span> n, i, fh;<br>        <span class="hljs-keyword">if</span> (tab == <span class="hljs-keyword">null</span> || (n = tab.length) == <span class="hljs-number">0</span>)<br>            tab = initTable();<br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((f = tabAt(tab, i = (n - <span class="hljs-number">1</span>) &amp; hash)) == <span class="hljs-keyword">null</span>) &#123;<br>            <span class="hljs-keyword">if</span> (casTabAt(tab, i, <span class="hljs-keyword">null</span>,<br>                         <span class="hljs-keyword">new</span> Node&lt;K,V&gt;(hash, key, value, <span class="hljs-keyword">null</span>)))<br>                <span class="hljs-keyword">break</span>;                   <span class="hljs-comment">// no lock when adding to empty bin</span><br>        &#125;<br>        <span class="hljs-comment">//发现此处为fwd节点，协助扩容，扩容结束后，再循环回来添加元素</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((fh = f.hash) == MOVED)<br>            tab = helpTransfer(tab, f);<br>        <br>        <span class="hljs-comment">//省略代码</span><br></code></pre></div></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">final</span> Node&lt;K,V&gt;[] helpTransfer(Node&lt;K,V&gt;[] tab, Node&lt;K,V&gt; f) &#123;<br>    Node&lt;K,V&gt;[] nextTab; <span class="hljs-keyword">int</span> sc;<br>    <span class="hljs-keyword">if</span> (tab != <span class="hljs-keyword">null</span> &amp;&amp; (f <span class="hljs-keyword">instanceof</span> ForwardingNode) &amp;&amp;<br>        (nextTab = ((ForwardingNode&lt;K,V&gt;)f).nextTable) != <span class="hljs-keyword">null</span>) &#123;<br>        <span class="hljs-keyword">int</span> rs = resizeStamp(tab.length);<br>        <span class="hljs-keyword">while</span> (nextTab == nextTable &amp;&amp; table == tab &amp;&amp;<br>               (sc = sizeCtl) &lt; <span class="hljs-number">0</span>) &#123;<br>            <span class="hljs-keyword">if</span> ((sc &gt;&gt;&gt; RESIZE_STAMP_SHIFT) != rs || sc == rs + <span class="hljs-number">1</span> ||<br>                sc == rs + MAX_RESIZERS || transferIndex &lt;= <span class="hljs-number">0</span>)<br>                <span class="hljs-keyword">break</span>;<br>            <span class="hljs-keyword">if</span> (U.compareAndSwapInt(<span class="hljs-keyword">this</span>, SIZECTL, sc, sc + <span class="hljs-number">1</span>)) &#123;<br>                <span class="hljs-comment">//扩容，传递一个不是null的nextTab</span><br>                transfer(tab, nextTab);<br>                <span class="hljs-keyword">break</span>;<br>            &#125;<br>        &#125;<br>        <span class="hljs-keyword">return</span> nextTab;<br>    &#125;<br>    <span class="hljs-keyword">return</span> table;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<h5 id="1-2、先添加元素，再协助扩容"><a href="#1-2、先添加元素，再协助扩容" class="headerlink" title="1.2、先添加元素，再协助扩容"></a>1.2、先添加元素，再协助扩容</h5><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">void</span> <span class="hljs-title">addCount</span><span class="hljs-params">(<span class="hljs-keyword">long</span> x, <span class="hljs-keyword">int</span> check)</span> </span>&#123;<br>    <span class="hljs-comment">//省略代码</span><br>    <br>    <span class="hljs-keyword">if</span> (check &gt;= <span class="hljs-number">0</span>) &#123;<br>        Node&lt;K,V&gt;[] tab, nt; <span class="hljs-keyword">int</span> n, sc;<br>  	    <span class="hljs-comment">//元素个数达到扩容阈值</span><br>        <span class="hljs-keyword">while</span> (s &gt;= (<span class="hljs-keyword">long</span>)(sc = sizeCtl) &amp;&amp; (tab = table) != <span class="hljs-keyword">null</span> &amp;&amp;<br>               (n = tab.length) &lt; MAXIMUM_CAPACITY) &#123;<br>            <span class="hljs-keyword">int</span> rs = resizeStamp(n);<br>            <span class="hljs-comment">//sizeCtl小于0，说明正在执行扩容，那么协助扩容，这里与helpTransfer()是一样的</span><br>            <span class="hljs-keyword">if</span> (sc &lt; <span class="hljs-number">0</span>) &#123;<br>                <span class="hljs-keyword">if</span> ((sc &gt;&gt;&gt; RESIZE_STAMP_SHIFT) != rs || sc == rs + <span class="hljs-number">1</span> ||<br>                    sc == rs + MAX_RESIZERS || (nt = nextTable) == <span class="hljs-keyword">null</span> ||<br>                    transferIndex &lt;= <span class="hljs-number">0</span>)<br>                    <span class="hljs-keyword">break</span>;<br>                <span class="hljs-keyword">if</span> (U.compareAndSwapInt(<span class="hljs-keyword">this</span>, SIZECTL, sc, sc + <span class="hljs-number">1</span>))<br>                    transfer(tab, nt); <span class="hljs-comment">// 这里传入 newTable</span><br>            &#125;<br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (U.compareAndSwapInt(<span class="hljs-keyword">this</span>, SIZECTL, sc,<br>                                         (rs &lt;&lt; RESIZE_STAMP_SHIFT) + <span class="hljs-number">2</span>))<br>                transfer(tab, <span class="hljs-keyword">null</span>); <span class="hljs-comment">// 这里传入空的 newTable 表示没有创建新数组</span><br>            s = sumCount();<br>        &#125;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<blockquote>
<p>注意：扩容的代码都在transfer方法中，这里不再赘述</p>
</blockquote>
<h4 id="2、图解-2"><a href="#2、图解-2" class="headerlink" title="2、图解"></a>2、图解</h4><p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/CHM1.8%E5%A4%9A%E7%BA%BF%E7%A8%8B%E6%89%A9%E5%AE%B9.png" srcset="/img/loading.gif" lazyload alt="CHM1.8多线程扩容"></p>
<h3 id="五、集合长度的累计方式"><a href="#五、集合长度的累计方式" class="headerlink" title="五、集合长度的累计方式"></a>五、集合长度的累计方式</h3><h4 id="1、源码分析-4"><a href="#1、源码分析-4" class="headerlink" title="1、源码分析"></a>1、源码分析</h4><h5 id="1-1、addCount方法"><a href="#1-1、addCount方法" class="headerlink" title="1.1、addCount方法"></a>1.1、addCount方法</h5><blockquote>
<p><strong>① CounterCell数组不为空，优先利用数组中的CounterCell记录数量</strong></p>
<p><strong>② 如果数组为空，尝试对baseCount进行累加，失败后，会执行fullAddCount逻辑</strong></p>
<p><strong>③ 如果是添加元素操作，会继续判断是否需要扩容</strong></p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">void</span> <span class="hljs-title">addCount</span><span class="hljs-params">(<span class="hljs-keyword">long</span> x, <span class="hljs-keyword">int</span> check)</span> </span>&#123;<br>    CounterCell[] as; <span class="hljs-keyword">long</span> b, s;<br>    <span class="hljs-comment">//当CounterCell数组不为空，则优先利用数组中的CounterCell记录数量</span><br>    <span class="hljs-comment">//或者当baseCount的累加操作失败，会利用数组中的CounterCell记录数量</span><br>    <span class="hljs-keyword">if</span> ((as = counterCells) != <span class="hljs-keyword">null</span> ||<br>        !U.compareAndSwapLong(<span class="hljs-keyword">this</span>, BASECOUNT, b = baseCount, s = b + x)) &#123;<br>        CounterCell a; <span class="hljs-keyword">long</span> v; <span class="hljs-keyword">int</span> m;<br>        <span class="hljs-comment">//标识是否有多线程竞争</span><br>        <span class="hljs-keyword">boolean</span> uncontended = <span class="hljs-keyword">true</span>;<br>        <span class="hljs-comment">//当as数组为空</span><br>        <span class="hljs-comment">//或者当as长度为0</span><br>        <span class="hljs-comment">//或者当前线程对应的as数组桶位的元素为空</span><br>        <span class="hljs-comment">//或者当前线程对应的as数组桶位不为空，但是累加失败</span><br>        <span class="hljs-keyword">if</span> (as == <span class="hljs-keyword">null</span> || (m = as.length - <span class="hljs-number">1</span>) &lt; <span class="hljs-number">0</span> ||<br>            (a = as[ThreadLocalRandom.getProbe() &amp; m]) == <span class="hljs-keyword">null</span> ||<br>            !(uncontended =<br>              U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) &#123;<br>            <span class="hljs-comment">//以上任何一种情况成立，都会进入该方法，传入的uncontended是false</span><br>            fullAddCount(x, uncontended);<br>            <span class="hljs-keyword">return</span>;<br>        &#125;<br>        <span class="hljs-keyword">if</span> (check &lt;= <span class="hljs-number">1</span>)<br>            <span class="hljs-keyword">return</span>;<br>        <span class="hljs-comment">//计算元素个数</span><br>        s = sumCount();<br>    &#125;<br>    <span class="hljs-keyword">if</span> (check &gt;= <span class="hljs-number">0</span>) &#123;<br>        Node&lt;K,V&gt;[] tab, nt; <span class="hljs-keyword">int</span> n, sc;<br>        <span class="hljs-comment">//当元素个数达到扩容阈值</span><br>        <span class="hljs-comment">//并且数组不为空</span><br>        <span class="hljs-comment">//并且数组长度小于限定的最大值</span><br>        <span class="hljs-comment">//满足以上所有条件，执行扩容</span><br>        <span class="hljs-keyword">while</span> (s &gt;= (<span class="hljs-keyword">long</span>)(sc = sizeCtl) &amp;&amp; (tab = table) != <span class="hljs-keyword">null</span> &amp;&amp;<br>               (n = tab.length) &lt; MAXIMUM_CAPACITY) &#123;<br>            <span class="hljs-comment">//这个是一个很大的正数</span><br>            <span class="hljs-keyword">int</span> rs = resizeStamp(n);<br>            <span class="hljs-comment">//sc小于0，说明有线程正在扩容，那么会协助扩容</span><br>            <span class="hljs-keyword">if</span> (sc &lt; <span class="hljs-number">0</span>) &#123;<br>                <span class="hljs-comment">//扩容结束或者扩容线程数达到最大值或者扩容后的数组为null或者没有更多的桶位需要转移，结束操作</span><br>                <span class="hljs-keyword">if</span> ((sc &gt;&gt;&gt; RESIZE_STAMP_SHIFT) != rs || sc == rs + <span class="hljs-number">1</span> ||<br>                    sc == rs + MAX_RESIZERS || (nt = nextTable) == <span class="hljs-keyword">null</span> ||<br>                    transferIndex &lt;= <span class="hljs-number">0</span>)<br>                    <span class="hljs-keyword">break</span>;<br>                <span class="hljs-comment">//扩容线程加1，成功后，进行协助扩容操作</span><br>                <span class="hljs-keyword">if</span> (U.compareAndSwapInt(<span class="hljs-keyword">this</span>, SIZECTL, sc, sc + <span class="hljs-number">1</span>))<br>                    <span class="hljs-comment">//协助扩容，newTable不为null</span><br>                    transfer(tab, nt);<br>            &#125;<br>            <span class="hljs-comment">//没有其他线程在进行扩容，达到扩容阈值后，给sizeCtl赋了一个很大的负数</span><br>            <span class="hljs-comment">//1+1=2 --》 代表此时有一个线程在扩容</span><br>            <br>            <span class="hljs-comment">//rs &lt;&lt; RESIZE_STAMP_SHIFT)是一个很大的负数</span><br>            <span class="hljs-comment">//rs左移16位，最高位是1，确保 sc 赋值为负数</span><br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (U.compareAndSwapInt(<span class="hljs-keyword">this</span>, SIZECTL, sc,<br>                                         (rs &lt;&lt; RESIZE_STAMP_SHIFT) + <span class="hljs-number">2</span>))<br>                <span class="hljs-comment">//扩容，newTable为null</span><br>                transfer(tab, <span class="hljs-keyword">null</span>);<br>            s = sumCount();<br>        &#125;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<h5 id="1-2、fullAddCount方法"><a href="#1-2、fullAddCount方法" class="headerlink" title="1.2、fullAddCount方法"></a>1.2、fullAddCount方法</h5><blockquote>
<p><strong>① 当CounterCell数组不为空，优先对CounterCell数组中的CounterCell的value累加</strong></p>
<p><strong>② 当CounterCell数组为空，会去创建CounterCell数组，默认长度为2，并对数组中的CounterCell的value累加</strong></p>
<p><strong>③ 当数组为空，并且此时有别的线程正在创建数组，那么尝试对baseCount做累加，成功即返回，否则自旋</strong></p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">void</span> <span class="hljs-title">fullAddCount</span><span class="hljs-params">(<span class="hljs-keyword">long</span> x, <span class="hljs-keyword">boolean</span> wasUncontended)</span> </span>&#123;<br>    <span class="hljs-keyword">int</span> h;<br>    <span class="hljs-comment">//获取当前线程的hash值</span><br>    <span class="hljs-keyword">if</span> ((h = ThreadLocalRandom.getProbe()) == <span class="hljs-number">0</span>) &#123;<br>        ThreadLocalRandom.localInit();      <span class="hljs-comment">// force initialization</span><br>        h = ThreadLocalRandom.getProbe();<br>        wasUncontended = <span class="hljs-keyword">true</span>;<br>    &#125;<br>    <span class="hljs-comment">//标识是否有冲突，如果最后一个桶不是null，那么为true</span><br>    <span class="hljs-keyword">boolean</span> collide = <span class="hljs-keyword">false</span>;                <span class="hljs-comment">// True if last slot nonempty</span><br>    <span class="hljs-keyword">for</span> (;;) &#123;<br>        CounterCell[] as; CounterCell a; <span class="hljs-keyword">int</span> n; <span class="hljs-keyword">long</span> v;<br>        <span class="hljs-comment">//数组不为空，优先对数组中CouterCell的value累加</span><br>        <span class="hljs-keyword">if</span> ((as = counterCells) != <span class="hljs-keyword">null</span> &amp;&amp; (n = as.length) &gt; <span class="hljs-number">0</span>) &#123;<br>            <span class="hljs-comment">//线程对应的桶位为null</span><br>            <span class="hljs-keyword">if</span> ((a = as[(n - <span class="hljs-number">1</span>) &amp; h]) == <span class="hljs-keyword">null</span>) &#123;<br>                <span class="hljs-keyword">if</span> (cellsBusy == <span class="hljs-number">0</span>) &#123;            <span class="hljs-comment">// Try to attach new Cell</span><br>                    <span class="hljs-comment">//创建CounterCell对象</span><br>                    CounterCell r = <span class="hljs-keyword">new</span> CounterCell(x); <span class="hljs-comment">// Optimistic create</span><br>                    <span class="hljs-comment">//利用CAS修改cellBusy状态为1，成功则将刚才创建的CounterCell对象放入数组中</span><br>                    <span class="hljs-keyword">if</span> (cellsBusy == <span class="hljs-number">0</span> &amp;&amp;<br>                        U.compareAndSwapInt(<span class="hljs-keyword">this</span>, CELLSBUSY, <span class="hljs-number">0</span>, <span class="hljs-number">1</span>)) &#123;<br>                        <span class="hljs-keyword">boolean</span> created = <span class="hljs-keyword">false</span>;<br>                        <span class="hljs-keyword">try</span> &#123;               <span class="hljs-comment">// Recheck under lock</span><br>                            CounterCell[] rs; <span class="hljs-keyword">int</span> m, j;<br>                            <span class="hljs-comment">//桶位为空， 将CounterCell对象放入数组</span><br>                            <span class="hljs-keyword">if</span> ((rs = counterCells) != <span class="hljs-keyword">null</span> &amp;&amp;<br>                                (m = rs.length) &gt; <span class="hljs-number">0</span> &amp;&amp;<br>                                rs[j = (m - <span class="hljs-number">1</span>) &amp; h] == <span class="hljs-keyword">null</span>) &#123;<br>                                rs[j] = r;<br>                                <span class="hljs-comment">//表示放入成功</span><br>                                created = <span class="hljs-keyword">true</span>;<br>                            &#125;<br>                        &#125; <span class="hljs-keyword">finally</span> &#123;<br>                            cellsBusy = <span class="hljs-number">0</span>;<br>                        &#125;<br>                        <span class="hljs-keyword">if</span> (created) <span class="hljs-comment">//成功退出循环</span><br>                            <span class="hljs-keyword">break</span>;<br>                        <span class="hljs-comment">//桶位已经被别的线程放置了已给CounterCell对象，继续循环</span><br>                        <span class="hljs-keyword">continue</span>;           <span class="hljs-comment">// Slot is now non-empty</span><br>                    &#125;<br>                &#125;<br>                collide = <span class="hljs-keyword">false</span>;<br>            &#125;<br>            <span class="hljs-comment">//桶位不为空，重新计算线程hash值，然后继续循环</span><br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (!wasUncontended)       <span class="hljs-comment">// CAS already known to fail</span><br>                wasUncontended = <span class="hljs-keyword">true</span>;      <span class="hljs-comment">// Continue after rehash</span><br>            <span class="hljs-comment">//重新计算了hash值后，对应的桶位依然不为空，对value累加</span><br>            <span class="hljs-comment">//成功则结束循环</span><br>            <span class="hljs-comment">//失败则继续下面判断</span><br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))<br>                <span class="hljs-keyword">break</span>;<br>            <span class="hljs-comment">//数组被别的线程改变了，或者数组长度超过了可用cpu大小，重新计算线程hash值，否则继续下一个判断</span><br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (counterCells != as || n &gt;= NCPU)<br>                collide = <span class="hljs-keyword">false</span>;            <span class="hljs-comment">// At max size or stale</span><br>            <span class="hljs-comment">//当没有冲突，修改为有冲突，并重新计算线程hash，继续循环</span><br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (!collide)<br>                collide = <span class="hljs-keyword">true</span>;<br>            <span class="hljs-comment">//如果CounterCell的数组长度没有超过cpu核数，对数组进行两倍扩容</span><br>            <span class="hljs-comment">//并继续循环</span><br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (cellsBusy == <span class="hljs-number">0</span> &amp;&amp;<br>                     U.compareAndSwapInt(<span class="hljs-keyword">this</span>, CELLSBUSY, <span class="hljs-number">0</span>, <span class="hljs-number">1</span>)) &#123;<br>                <span class="hljs-keyword">try</span> &#123;<br>                    <span class="hljs-keyword">if</span> (counterCells == as) &#123;<span class="hljs-comment">// Expand table unless stale</span><br>                        CounterCell[] rs = <span class="hljs-keyword">new</span> CounterCell[n &lt;&lt; <span class="hljs-number">1</span>];<br>                        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n; ++i)<br>                            rs[i] = as[i];<br>                        counterCells = rs;<br>                    &#125;<br>                &#125; <span class="hljs-keyword">finally</span> &#123;<br>                    cellsBusy = <span class="hljs-number">0</span>;<br>                &#125;<br>                collide = <span class="hljs-keyword">false</span>;<br>                <span class="hljs-keyword">continue</span>;                   <span class="hljs-comment">// Retry with expanded table</span><br>            &#125;<br>            h = ThreadLocalRandom.advanceProbe(h);<br>        &#125;<br>        <span class="hljs-comment">//CounterCell数组为空，并且没有线程在创建数组，修改标记，并创建数组</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (cellsBusy == <span class="hljs-number">0</span> &amp;&amp; counterCells == as &amp;&amp;<br>                 U.compareAndSwapInt(<span class="hljs-keyword">this</span>, CELLSBUSY, <span class="hljs-number">0</span>, <span class="hljs-number">1</span>)) &#123;<br>            <span class="hljs-keyword">boolean</span> init = <span class="hljs-keyword">false</span>;<br>            <span class="hljs-keyword">try</span> &#123;                           <span class="hljs-comment">// Initialize table</span><br>                <span class="hljs-keyword">if</span> (counterCells == as) &#123;<br>                    CounterCell[] rs = <span class="hljs-keyword">new</span> CounterCell[<span class="hljs-number">2</span>];<br>                    rs[h &amp; <span class="hljs-number">1</span>] = <span class="hljs-keyword">new</span> CounterCell(x);<br>                    counterCells = rs;<br>                    init = <span class="hljs-keyword">true</span>;<br>                &#125;<br>            &#125; <span class="hljs-keyword">finally</span> &#123;<br>                cellsBusy = <span class="hljs-number">0</span>;<br>            &#125;<br>            <span class="hljs-keyword">if</span> (init)<br>                <span class="hljs-keyword">break</span>;<br>        &#125;<br>        <span class="hljs-comment">//数组为空，并且有别的线程在创建数组，那么尝试对baseCount做累加，成功就退出循环，失败就继续循环</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (U.compareAndSwapLong(<span class="hljs-keyword">this</span>, BASECOUNT, v = baseCount, v + x))<br>            <span class="hljs-keyword">break</span>;                          <span class="hljs-comment">// Fall back on using base</span><br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<h4 id="2、图解-3"><a href="#2、图解-3" class="headerlink" title="2、图解"></a>2、图解</h4><blockquote>
<p>fullAddCount方法中，当as数组不为空的逻辑图解</p>
</blockquote>
<p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/CHM1.8%E9%9B%86%E5%90%88%E9%95%BF%E5%BA%A6%E8%8E%B7%E5%8F%96.png" srcset="/img/loading.gif" lazyload alt="CHM1.8集合长度获取"></p>
<h3 id="六、jdk1-8集合长度获取"><a href="#六、jdk1-8集合长度获取" class="headerlink" title="六、jdk1.8集合长度获取"></a>六、jdk1.8集合长度获取</h3><ul>
<li><code>size</code> 的获取，如果线程可以将大小直接加入到 <code>baseCount</code> 则结束</li>
<li>否则就尝试加到 <code>counterCells</code> 里，此数组会有扩容机制。加不进去，则随机加入到 <code>counterCells</code> 的其他位置，这点在 <code>fullAddCount</code> 有体现出来</li>
</ul>
<h4 id="1、源码分析-5"><a href="#1、源码分析-5" class="headerlink" title="1、源码分析"></a>1、源码分析</h4><h5 id="1-1、size方法"><a href="#1-1、size方法" class="headerlink" title="1.1、size方法"></a>1.1、size方法</h5><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">size</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">long</span> n = sumCount();<br>    <span class="hljs-keyword">return</span> ((n &lt; <span class="hljs-number">0L</span>) ? <span class="hljs-number">0</span> :<br>            (n &gt; (<span class="hljs-keyword">long</span>)Integer.MAX_VALUE) ? Integer.MAX_VALUE :<br>            (<span class="hljs-keyword">int</span>)n);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<h5 id="1-2、sumCount方法"><a href="#1-2、sumCount方法" class="headerlink" title="1.2、sumCount方法"></a>1.2、sumCount方法</h5><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">final</span> <span class="hljs-keyword">long</span> <span class="hljs-title">sumCount</span><span class="hljs-params">()</span> </span>&#123;<br>    CounterCell[] as = counterCells; CounterCell a;<br>    <span class="hljs-comment">//获取baseCount的值</span><br>    <span class="hljs-keyword">long</span> sum = baseCount;<br>    <span class="hljs-keyword">if</span> (as != <span class="hljs-keyword">null</span>) &#123;<br>        <span class="hljs-comment">//遍历CounterCell数组，累加每一个CounterCell的value值</span><br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; as.length; ++i) &#123;<br>            <span class="hljs-keyword">if</span> ((a = as[i]) != <span class="hljs-keyword">null</span>)<br>                sum += a.value;<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">return</span> sum;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<blockquote>
<p>注意：这个方法并不是线程安全的</p>
</blockquote>
<h2 id="🔗Reference"><a href="#🔗Reference" class="headerlink" title="🔗Reference"></a>🔗Reference</h2><blockquote>
<p><a target="_blank" rel="noopener" href="https://www.bilibili.com/video/BV17i4y1x71z">https://www.bilibili.com/video/BV17i4y1x71z</a></p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/woaiwym/article/details/80675789">https://blog.csdn.net/woaiwym/article/details/80675789</a></p>
<p><a target="_blank" rel="noopener" href="https://www.cnblogs.com/lonely-wolf/p/14502194.html">https://www.cnblogs.com/lonely-wolf/p/14502194.html</a></p>
<p><a target="_blank" rel="noopener" href="https://segmentfault.com/a/1190000021237438">https://segmentfault.com/a/1190000021237438</a></p>
</blockquote>

            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/JavaSE/">JavaSE</a>
                    
                  </div>
                
                
              </div>
              
                <p class="note note-warning">
                  
                    本博客所有文章除特别声明外，均采用 <a target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！
                  
                </p>
              
              
                <div class="post-prevnext">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2021/09/18/JavaSE/%E5%85%B3%E4%BA%8E%E8%AE%BE%E8%AE%A1%E7%BB%9D%E5%AF%B9%E5%80%BCabs%E7%9A%84%E4%B8%80%E4%BA%9B%E6%80%9D%E8%80%83/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">关于设计绝对值abs的一些思考</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2021/08/16/JavaSE/Java%E5%B8%B8%E7%94%A8%E9%9B%86%E5%90%88%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90%20%E2%85%A1/">
                        <span class="hidden-mobile">Java常用集合源码分析 Ⅱ</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div class="toc-body" id="toc-body"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    

    
      <a id="scroll-top-button" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
    

    
  </main>

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     © 2019-2021 
  </div>
  
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


  

  
</footer>


  <!-- SCRIPTS -->
  
  <script  src="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js" ></script>
<script  src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/img-lazyload.js" ></script>
  



  



  <script  src="https://cdn.jsdelivr.net/npm/tocbot@4.12.0/dist/tocbot.min.js" ></script>



  <script  src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js" ></script>



  <script  src="https://cdn.jsdelivr.net/npm/anchor-js@4.3.0/anchor.min.js" ></script>



  <script defer src="https://cdn.jsdelivr.net/npm/clipboard@2.0.6/dist/clipboard.min.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>




  <script  src="https://cdn.jsdelivr.net/npm/typed.js@2.0.11/lib/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var title = document.getElementById('subtitle').title;
      
      typing(title)
      
    })(window, document);
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    (function () {
      var path = "/local-search.xml";
      $('#local-search-input').on('click', function() {
        searchFunc(path, 'local-search-input', 'local-search-result');
      });
      $('#modalSearch').on('shown.bs.modal', function() {
        $('#local-search-input').focus();
      });
    })()
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.jsdelivr.net/npm/mathjax@3.1.2/es5/tex-svg.js" ></script>

  











<!-- 主题的启动项 保持在最底部 -->
<script  src="/js/boot.js" ></script>


</body>
</html>
